Département d’informatique. Partiel de mathématiques discrètes. Semestre 1 (Novembre 09).

Seule une fiche manuscrite de format A5 est autorisée.

Nom :  ..............................
Prénom : ..............................

1 QCM

Cette partie contient 47 affirmations. Vous aurez +1 à chaque valeur de vérité trouvée, -1 à chaque erreur (et 0 en absence de réponse). Les notes seront ajustées à l’intervalle [0; 20] (les notes négatives auront 0).

Q. 1. Le nombre π est rationnel. L’assertion proposée est vraie ou fausse ? Q. 2. Soit A = {{a, b}, {c}, {d, e, f}}. On a a ∈ A. L’assertion proposée est vraie ou fausse ? Q. 3. L’intersection entre deux ensembles est l’ensemble des éléments appartenant aux deux ensembles.

L’assertion proposée est vraie ou fausse ?

Q. 4. Soit A = {{a, b}, {c}, {d, e, f}}. On a {d, e, f} ∈ A. L’assertion proposée est vraie ou fausse ? Q. 5. L’intersection de deux ensembles est l’ensemble des éléments appartenant à au moins un des deux en-

sembles. L’assertion proposée est vraie ou fausse ?

Q. 6. Le complémentaire de l’ensemble des entiers positifs ou nuls dans ℕ est égal à l’ensemble des entiers strictement négatifs. L’assertion proposée est vraie ou fausse ?

Q. 7. Soit t_{1} et t_{2} deux termes exprimés dans une algèbre de Boole munie des opérateurs classiques +, .et . Si t_{1}.t_{2} = 0 alors t_{1} = \overline{t_{2}}. L’assertion proposée est vraie ou fausse ?

Q. 8. Soit t_{1} et t_{2} deux termes exprimés dans une algèbre de Boole munie des opérateurs classiques +, .et . Si t_{1}.t_{2} = 0 alors t_{1} ou t_{2} sont nuls. L’assertion proposée est vraie ou fausse ?

Q. 9. Soit A = {{a, b}, {c}, {d, e, f}}. P (A) contient 8 éléments. L’assertion proposée est vraie ou fausse ? Q. 10. Le complémentaire de A dans E est l’ensemble des éléments de E qui ne sont pas dans A. L’assertion

proposée est vraie ou fausse ?

Q. 11. Par convention, ∅ a 0 élément. L’assertion proposée est vraie ou fausse ? Q. 12. La réunion de deux ensembles A et B est l’ensemble des éléments appartenant à A ou à B. L’assertion

proposée est vraie ou fausse ?

Q. 13. Le cardinal d’un ensemble fini est son nombre d’éléments. L’assertion proposée est vraie ou fausse ? Q. 14. Il existe un unique ensemble vide. L’assertion proposée est vraie ou fausse ? Q. 15. On considère 4 variables booléennes a, b, c et d. Le + est le symbole du OU logique non exclusif, le

. est le symbole du ET logique et est la négation logique. L’égalité \overline{a}.b.\overline{c}.\overline{d} = 1 est établie si et seulement si a + \overline{b} + c + d = 0. L’assertion proposée est vraie ou fausse ?

Q. 16. Soit A = {{a, b}, {c}, {d, e, f}}. P (A) contient 3 éléments. L’assertion proposée est vraie ou fausse ? Q. 17. Le complémentaire de A dans E est l’ensemble des éléments de E qui ne sont pas dans A. L’assertion

proposée est vraie ou fausse ?

Q. 18. Le complémentaire des entiers pairs dans ℕ est égal à l’ensemble des entiers impairs. L’assertion proposée est vraie ou fausse ?

Q. 19. Le nombre π est irrationnel. L’assertion proposée est vraie ou fausse ? Q. 20. Soit A = {{a, b}, {c}, {d, e, f}}. {c} ⊂ A. L’assertion proposée est vraie ou fausse ? Q. 21. On considère 4 variables booléennes a, b, c et d. Le + est le symbole du OU logique non exclusif, le .

est le symbole du ET logique et est la négation logique. L’expression \overline{a} + \overline{b} + c + d vaut 1 si et seulement a.b vaut 0. L’assertion proposée est vraie ou fausse ?

Q. 22. Soit A = {{a, b}, {c}, {d, e, f}}. P (A) contient 4 éléments. L’assertion proposée est vraie ou fausse ? Q. 23. Le complémentaire de A dans E est l’ensemble des éléments de A qui ne sont pas dans E. L’assertion

proposée est vraie ou fausse ?

Q. 24. ℕ est un ensemble infini. L’assertion proposée est vraie ou fausse ? Q. 25. Soit A = {{a, b}, {c}, {d, e, f}}. On a ∅ ⊂ A. L’assertion proposée est vraie ou fausse ? Q. 26. sin(1) est irrationnel. L’assertion proposée est vraie ou fausse ? Q. 27. Soit A = {{a, b}, {c}, {d, e, f}}. On a ∅ ∈ A. L’assertion proposée est vraie ou fausse ? Q. 28. ℤ est un ensemble infini. L’assertion proposée est vraie ou fausse ? Q. 29. On considère 4 variables booléennes a, b, c et d. Le + est le symbole du OU logique non exclusif, le .

est le symbole du ET logique et est la négation logique. L’expression a+\overline{b}+\overline{a}.b+\overline{c} est égale à \overline{c}+1. L’assertion proposée est vraie ou fausse ?

Q. 30. La réunion de deux ensembles A et B est l’ensemble des éléments appartenant à A et à B. L’assertion proposée est vraie ou fausse ?

Q. 31. A ∪ B est la réunion de A et de B. L’assertion proposée est vraie ou fausse ? Q. 32. On considère 4 variables booléennes a, b, c et d. Le + est le symbole du OU logique non exclusif, le .

est le symbole du ET logique et est la négation logique. L’égalité a + \overline{b} + \overline{c} + \overline{d} = 0 est établie si et seulement si a est la seule variable valant 0. L’assertion proposée est vraie ou fausse ?

Q. 33. A ∪ B est l’intersection de A et de B. L’assertion proposée est vraie ou fausse ? Q. 34. A ∩ B est la réunion de A et de B. L’assertion proposée est vraie ou fausse ? Q. 35. e est irrationnel. L’assertion proposée est vraie ou fausse ? Q. 36. On considère 4 variables booléennes a, b, c et d. Le + est le symbole du OU logique non exclusif, le

. est le symbole du ET logique et est la négation logique. L’expression \overline{a}.b + a.\overline{b} est vraie quand a et b sont différents. L’assertion proposée est vraie ou fausse ?

Q. 37. La réunion entre deux ensembles est l’ensemble des éléments appartenant aux deux ensembles. L’assertion proposée est vraie ou fausse ?

Q. 38. Dans une algèbre de Boole munie des opérateurs classiques +, .et , on considère l’expression E = \overline{a}.b + a.c + \overline{b}.c + \overline{c}. La version la plus réduite de E est 0. L’assertion proposée est vraie ou fausse ?

Q. 39. On considère 4 variables booléennes a, b, c et d. Le + est le symbole du OU logique non exclusif, le . est le symbole du ET logique et est la négation logique. L’expression \overline{a} + \overline{b} + c + d vaut 1 si et seulement c.d vaut 1. L’assertion proposée est vraie ou fausse ?

Q. 40. sin(1) est rationnel. L’assertion proposée est vraie ou fausse ? Q. 41. L’intersection de deux ensembles A et B est l’ensemble des éléments appartenant à A ou à B. L’asser-

tion proposée est vraie ou fausse ?

Q. 42. A ∩ B est l’intersection de A et B. L’assertion proposée est vraie ou fausse ? Q. 43. Le complémentaire de l’ensemble des entiers positifs ou nuls dans ℕ est égal à l’ensemble des entiers

strictement négatifs. L’assertion proposée est vraie ou fausse ?

Q. 44. Dans une algèbre de Boole munie des opérateurs classiques +, .et , on considère l’expression E = \overline{a}(a + b)(a + c)(a + d)(a + e). La version la plus réduite de E est 1. L’assertion proposée est vraie ou fausse ?

Q. 45. Dans une algèbre de Boole munie des opérateurs classiques +, .et , on considère l’expression E = \overline{a}.b + a.c + \overline{b}.c + \overline{c}. La version la plus réduite de E est 1. L’assertion proposée est vraie ou fausse ?

Q. 46. Soit A = {{a, b}, {c}, {d, e, f}}. On a {{a, b}} ⊂ A. L’assertion proposée est vraie ou fausse ? Q. 47. Soit A = {{a, b}, {c}, {d, e, f}}. L’ensemble P (A) contient 64 éléments. L’assertion proposée est

vraie ou fausse ?

Numéro V F Numéro V F Numéro V F
Q. 1  Q. 2  Q. 3
Q. 4  Q. 5  Q. 6
Q. 7  Q. 8  Q. 9
Q. 10  Q. 11  Q. 12
Q. 13  Q. 14  Q. 15
Q. 16  Q. 17  Q. 18
Q. 19  Q. 20  Q. 21
Q. 22  Q. 23  Q. 24
Q. 25  Q. 26  Q. 27
Q. 28  Q. 29  Q. 30
Q. 31  Q. 32  Q. 33
Q. 34  Q. 35  Q. 36
Q. 37  Q. 38  Q. 39
Q. 40  Q. 41  Q. 42
Q. 43  Q. 44  Q. 45
Q. 46  Q. 47

2 Problèmes

2.1 Théorie des ensembles

Rappel : pour deux ensembles A et B, on appelle différence symétrique, noté AΔB, l’ensemble défini par

AΔB = (A ∪ B) \ (A ∩ B)

c’est-à-dire que AΔB est constitué des éléments qui appartiennent soit à A, soit à B, mais pas aux deux. Soit A, B et C trois ensembles.

1. Montrer que l’opérateur est commutatif.

2. Montrer que l’opérateur possède un élément neutre que l’on explicitera.

3. Montrer que si AΔB = AΔC alors B = C.

2.2 Algèbre de Boole 1

A l’aide des méthodes de votre choix (Karnaugh ou consensus), réécrire les expression suivantes en une somme qui contient le moins de monômes.

1. A = \overline{c}\overline{d}b + cab + \overline{c}dab + c\overline{d}\overline{a}b + ca\overline{b}.

2. B = \overline{a}b\overline{c}\overline{d} + ab\overline{c} + a\overline{b}\overline{c}d + acd + abc\overline{d} + \overline{a}\overline{b}d

2.3 Algèbre de Boole 2

On considère le jeu avec une équipe de quatre candidats dont un chef d’équipe. Chaque candidat dispose d’un boîtier lui permettant de donner un vote de type oui/non. Un affichage central présente l’avis de la majorité des candidats. Lorsqu’il y a le même nombre de votes « oui » que de votes « non » le vote du chef d’équipe est prépondérant.

1. Construire la table de vérité du système central d’affichage ;

2. Exprimez l’affichage centrale en FCD ;

3. Formez une expression booléenne minimale de l’affichage.